package main

func main() {

	//root = [4,2,9,3,5,null,7]
	node3 := TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node5 := TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node1 := TreeNode{
		Val:   2,
		Left:  &node3,
		Right: &node4,
	}
	node2 := TreeNode{
		Val:   9,
		Left:  nil,
		Right: &node5,
	}
	root := TreeNode{
		Val:   4,
		Left:  &node1,
		Right: &node2,
	}

	//打印测试用例返回结果
	resp := findTilt(&root)
	println(resp)

}

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func findTilt(root *TreeNode) int {
	ans, _ := dfs(root)
	return ans
}

//利用Go语言的双返回值机制做这个题(其他语言也不是不行，返回一个数组就可以了)
func dfs(node *TreeNode) (int, int) { //第一个返回值返回整个树的坡度，第二个返回值返回该节点及其子子孙孙的累加和
	if node == nil {
		return 0, 0
	}
	leftAns, sumLeft := dfs(node.Left)
	rightAns, sumRight := dfs(node.Right)

	ans := abs(sumLeft-sumRight) + leftAns + rightAns
	return ans, sumLeft + sumRight + node.Val

}

//求绝对值
func abs(num int) int {
	if num >= 0 {
		return num
	} else {
		return -num
	}
}
